package org.labuladong.动态规划算法.背包问题;

/**
 * @Author: qingle
 * @Date: 2024/10/28-16:11
 * @Description: ⼦集背包问题
 * @version: 1.0
 */
public class LC_子背包问题 {

	public static void main(String[] args) {

		int[] nums = {1, 5, 11, 5};
		System.out.println(canPartition(nums));
	}

	static boolean canPartition(int[] nums) {
		int sum = 0;
		for (int num : nums) sum += num;
		// 和为奇数时，不可能划分成两个和相等的集合
		if (sum % 2 != 0) return false;
		int n = nums.length;
		sum = sum / 2;
		boolean[][] dp = new boolean[n + 1][sum + 1];
		// base case
		for (int i = 0; i <= n; i++)
			dp[i][0] = true;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= sum; j++) {
				if (j - nums[i - 1] < 0) {
					// 背包容量不⾜，不能装⼊第 i 个物品
					dp[i][j] = dp[i - 1][j];
				} else {
					// 装⼊或不装⼊背包
					dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
				}
			}
		}
		return dp[n][sum];
	}
}
